Questions taken from:

http://mycsinterviewsexperiences.blogspot.com/2012/09/interviews-with-microsoft-bing-and.html



In [1]:

    
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}



In [2]:

    
def dfs(graph, start):
    visited, stack = (set(), [start])
    while stack:
        curr = stack.pop()
        print "Outside: ", curr, "->", visited, stack
        if curr not in visited:
            visited.add(curr)
            stack.extend(graph[curr] - visited)
    return visited
            
           
            
dfs(graph, "A")









    



Outside:  A -> set([]) []
Outside:  B -> set(['A']) ['C']
Outside:  D -> set(['A', 'B']) ['C', 'E']
Outside:  E -> set(['A', 'B', 'D']) ['C']
Outside:  F -> set(['A', 'B', 'E', 'D']) ['C']
Outside:  C -> set(['A', 'B', 'E', 'D', 'F']) ['C']
Outside:  C -> set(['A', 'C', 'B', 'E', 'D', 'F']) []






    Out[2]:





{'A', 'B', 'C', 'D', 'E', 'F'}



In [3]:

    
def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        curr, path = stack.pop()
        for next in graph[curr] - set(path):
            if next == goal:
                print path + [next]
            else:
                stack.append((next, path + [next]))
                
dfs_paths(graph, "A", "F")









    



['A', 'B', 'E', 'F']
['A', 'C', 'F']



In [4]:

    
def bfs(graph, start):
    visited, queue = (set(), [start])
    while queue:
        print "Visited: %s, Queue: %s" % (visited, queue)
        curr = queue.pop(0)
        print "Outside: ", curr
        if curr not in visited:
            visited.add(curr)
            for k in graph[curr] - visited:
                queue.extend(graph[k] - visited)
            visited = visited.union(graph[curr])
            #print "Curr: %s, Edges: %s" % (curr, graph[curr])
    return visited

bfs(graph, "A")









    



Visited: set([]), Queue: ['A']
Outside:  A
Visited: set(['A', 'C', 'B']), Queue: ['F', 'E', 'D']
Outside:  F
Visited: set(['A', 'C', 'B', 'E', 'F']), Queue: ['E', 'D']
Outside:  E
Visited: set(['A', 'C', 'B', 'E', 'F']), Queue: ['D']
Outside:  D






    Out[4]:





{'A', 'B', 'C', 'D', 'E', 'F'}



In [5]:

    
def bfs(graph, start):
    visited, queue = (set(), [start])
    while queue:
        print "Visited: %s, Queue: %s" % (visited, queue)
        curr = queue.pop(0)
        print "Outside: ", curr
        if curr not in visited:
            visited.add(curr)
            queue.extend(graph[curr] - visited)
    return visited

bfs(graph, "A")









    



Visited: set([]), Queue: ['A']
Outside:  A
Visited: set(['A']), Queue: ['C', 'B']
Outside:  C
Visited: set(['A', 'C']), Queue: ['B', 'F']
Outside:  B
Visited: set(['A', 'C', 'B']), Queue: ['F', 'E', 'D']
Outside:  F
Visited: set(['A', 'C', 'B', 'F']), Queue: ['E', 'D', 'E']
Outside:  E
Visited: set(['A', 'C', 'B', 'E', 'F']), Queue: ['D', 'E']
Outside:  D
Visited: set(['A', 'C', 'B', 'E', 'D', 'F']), Queue: ['E']
Outside:  E






    Out[5]:





{'A', 'B', 'C', 'D', 'E', 'F'}



In [6]:

    
def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        curr, path = queue.pop(0)
        for next in graph[curr] - set(path):
            if next == goal:
                print path + [next]
            else:
                queue.append((next, path + [next]))

bfs_paths(graph, "A", "F")









    



['A', 'C', 'F']
['A', 'B', 'E', 'F']



In [7]:

    
def shortest_path(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        curr, path = queue.pop(0)
        for next in graph[curr] - set(path):
            if next == goal:
                return path + [next]
            else:
                queue.append((next, path + [next]))
    return None
for k in graph.keys():
    print "A", k, shortest_path(graph, "A", k)









    



A A None
A C ['A', 'C']
A B ['A', 'B']
A E ['A', 'B', 'E']
A D ['A', 'B', 'D']
A F ['A', 'C', 'F']

Q1. Given a binary tree, return true if it is a BST. Do it in a non-recursive way.

Do DFS and at each step check the condition for BST. If fail return False. If passes all conditions return True.



In [8]:

    
def append_bst(graph, root, item):
    if root is None:
        graph[item] = [None, None]
        return graph
    curr = root
    while (item < curr) or (item > curr):
        if item < curr:
            if graph[curr][0] is not None:
                curr = graph[curr][0]
            else:
                graph[curr][0] = item
                graph[item] = [None, None]
        elif item > curr:
            if graph[curr][1] is not None:
                curr = graph[curr][1]
            else:
                graph[curr][1] = item
                graph[item] = [None, None]
    return graph

def gen_bst(arr):
    graph = append_bst({}, None, arr[0])
    root = arr[0]
    for item in arr[1:]:
        graph = append_bst(graph, root, item)
        #print item, graph
    return graph, root



In [9]:

    
print "Final graph:\n", gen_bst(range(10))









    



Final graph:
({0: [None, 1], 1: [None, 2], 2: [None, 3], 3: [None, 4], 4: [None, 5], 5: [None, 6], 6: [None, 7], 7: [None, 8], 8: [None, 9], 9: [None, None]}, 0)



In [10]:

    
print "Final graph:\n", gen_bst([4,5,3,2,10,1,7])









    



Final graph:
({1: [None, None], 2: [1, None], 3: [2, None], 4: [3, 5], 5: [None, 10], 7: [None, None], 10: [7, None]}, 4)



In [11]:

    
def print_graph(graph, root):
    visited, queue = (set([None]), [root])
    level = 0
    while queue:
        curr = queue.pop(0)
        print curr 
        if curr not in visited:
            visited.add(curr)
            queue.extend(set(graph[curr]) - visited)



In [12]:

    
print_graph(*gen_bst([4,5,3,2,10,1,7]))



In [13]:

    
min([1, 2, 3])









    Out[13]:





1



In [14]:

    
def is_bst(graph, root):
    if root is None:
        return True
    visited, stack = (set([None]), [root])
    while stack:
        curr = stack.pop()
        left, right = graph[curr]
        if left is not None and left > curr:
            # Left is always smaller than parent
            return False
        if right is not None and right < curr:
            # Right is always greater than parent
            return False
        if curr not in visited:
            visited.add(curr)
            print curr
            stack.extend(set(graph[curr]) - visited)
    return True



In [15]:

    
graph, root = gen_bst([4,5,3,2,10,1,7])
is_bst(graph, root)



In [16]:

    
graph = {0: [1,2],
         1: [None, None],
         2: [None, None]}
root = 0
is_bst(graph, root)









    Out[16]:





False

Q2. There is a 2D matrix of size 10 X 10, where you have to begin from the location (0,0) and move to the location (9,9). You can either move right on down. Find out the number of distinct paths in which you can reach (9,9) from (0,0).

paths(i,j) = #paths(i-1, j-1) + 2



In [17]:

    
def npaths(N=10):
    mat = [[0]*N for k in range(N)]
    mat[0][0] = 1
    for i in range(N):
        for j in range(N):
            if mat[i][j] == 0:
                if i == 0:
                    mat[i][j] = mat[i][j-1] # Only one movement from left cell
                    #print "mat[%s][%s] = mat[%s][%s]" % (i,j,i,j-1)
                    #print_mat(mat)
                elif j == 0:
                    mat[i][j] = mat[i-1][j] # Only one movement from top cell
                    #print "mat[%s][%s] = mat[%s][%s]" % (i,j,i-1,j)
                else:
                    mat[i][j] = mat[i-1][j] + mat[i][j-1]
                    #print "mat[%s][%s] = mat[%s][%s]+1" % (i,j,i-1,j-1)
    return mat

def print_mat(mat):
    for row in mat:
        print row



In [18]:

    
print_mat(npaths(N=2))









    



[1, 1]
[1, 2]



In [19]:

    
print_mat(npaths(N=3))









    



[1, 1, 1]
[1, 2, 3]
[1, 3, 6]



In [20]:

    
print_mat(npaths(N=10))









    



[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
[1, 4, 10, 20, 35, 56, 84, 120, 165, 220]
[1, 5, 15, 35, 70, 126, 210, 330, 495, 715]
[1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002]
[1, 7, 28, 84, 210, 462, 924, 1716, 3003, 5005]
[1, 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440]
[1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310]
[1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620]

Q3. Given an array with a special property, find the smallest number in it. The special property is that the elements in the array are monotonically decreasing and then increasing.

Get middle element:

if middle element part of increasing sequence then search left
if middle element part of decreasing sequence then search right

Stop when middle number such that left is higher and right is higher



In [21]:

    
def find_smallest(arr):
    left, right = 0, len(arr)
    mid = (left + right) /2
    i = 1
    while mid > 0 and mid < len(arr)-1 and i < len(arr):
        if arr[mid-1] <= arr[mid] and arr[mid+1] >= arr[mid]:
            right = mid
        elif arr[mid-1] >= arr[mid] and arr[mid+1] <= arr[mid]:
            left = mid
        else:
            break
        mid = (left + right) /2
        i += 1
    print "Iterations required: ", i
    return arr[mid]



In [22]:

    
find_smallest([1])









    



Iterations required:  1






    Out[22]:





1



In [23]:

    
find_smallest([1,2,3])









    



Iterations required:  2






    Out[23]:





1



In [24]:

    
find_smallest([10,9,8,7,11,12,13,14])









    



Iterations required:  3






    Out[24]:





7



In [25]:

    
find_smallest([3,2,1])









    



Iterations required:  2






    Out[25]:





1

Find if a string s3 can be formed by interleaving 2 other given strings s1 and s2

Characters of each string s1 and s2 will appear in the same order they appear in the original string. All characters of s1 and s2 must be exhausted.

E.g.

s1 = "aaab"
s2 = "aaac"
s3 = "aaaacaab" # is_interleaved = True
s3 = "aaaacaa" # is_interleaved = False, as b is not present in s3
s3 = "aaaacaad" # is_interleaved = False, as d is not present in s1 or s2

Approach: If s[i+j] can be formed by inteleaving s1[i-1] and s2[j] or s1[i] and s2[j-1] then s3[i+j+1] can just be formed by just matching the next character.



In [34]:

    
from pprint import pprint



In [141]:

    
mat = []

def f(s1,s2,s3,i,j):
    if i < 0 and j < 0:
        return True
    if i < 0:
        return (s3[:j+1] == s2[:j+1])
    if j < 0:
        return (s3[:i+1] == s1[:i+1])
    if mat[i][j] == -1:
        mat[i][j] = (
            (f(s1,s2,s3,i-1,j) and (s3[i+j+1] == s1[i]))
            or (f(s1,s2,s3,i,j-1) and (s3[i+j+1] == s2[j]))
        )
    return mat[i][j]

def is_interleaved(s1,s2,s3):
    global mat
    if len(s1) == 0 and len(s2) == 0 and len(s3) == 0:
        return True
    if len(s3) != (len(s1) + len(s2)):
        return False
    l_s1, l_s2 = len(s1), len(s2)
    mat = [[-1]*(l_s2) for i in xrange(l_s1)]
    for i in xrange(l_s1):
        for j in xrange(l_s2):
            check = f(s1,s2,s3,i,j)
            #print i,j, i+j+1, s1[:i+1], s2[:j+1], s3[:i+j+2], check
    #pprint(mat)
    return mat[-1][-1]



In [142]:

    
s1 = "aaab"
s2 = "aaac"
for s3 in ["aaaacaab", "aaaacaa", "aaaacaad", "aaaadaad", ""]:
    print "'%s'\t%s" % (s3, is_interleaved(s1, s2, s3))









    



'aaaacaab'	True
'aaaacaa'	False
'aaaacaad'	False
'aaaadaad'	False
''	False



In [143]:

    
s1 = "hello"
s2 = "world"
for s3 in ["worldhello", "heworlllod", "helloworld", ""]:
    print "'%s'\t%s" % (s3, is_interleaved(s1, s2, s3))









    



'worldhello'	True
'heworlllod'	True
'helloworld'	True
''	False



In [144]:

    
s1 = ""
s2 = ""
for s3 in ["worldhello", "heworlllod", "helloworld", ""]:
    print "'%s'\t%s" % (s3, is_interleaved(s1, s2, s3))









    



'worldhello'	False
'heworlllod'	False
'helloworld'	False
''	True



In [124]:

    
pprint(mat)

[]



In [ ]: